1. Field of the Invention
This invention relates generally to the optical scanning of two dimensional bar code symbols and in particular to the optical scanning of a randomly oriented two-dimensional bar code symbol by first determining the orientation oil the symbol with respect to the field of view of the scanning device and then rotating the field of view accordingly so as to be aligned substantially with the symbol for scanning and further processing and decoding.
2. Description of Related Art
Bar codes have become broadly accepted as a means for automatically identifying objects. A bar code symbol is a pattern of parallel bars and spaces of various widths that represent data elements or characters. The bars represent strings of binary ones and the spaces represent strings of binary zeros. Generally, the bars and spaces can be no smaller than a specified minimum width which is called a "module" or "unit." The bars and spaces are multiples of this module size or minimum width.
The conventional bar code symbol is "one-dimensional" in that the bars and spaces extend only in a single direction. There has been an increasing need, however, for machine-readable symbols that contain more information than conventional bar code symbols. One approach for increasing the information in machine-readable symbols is to reduce the height of the bar codes and stack the bar codes one on top of each other to create a "stacked" or "two-dimensional" bar code. One such two-dimensional bar code is PDF417, which was developed by Symbol Technologies, Inc. The PDF417 symbology utilizes a variable number of codewords which are discrete representations of data. A complete description of the PDF417 code is contained in U.S. Pat. No. 5,304,786, which is assigned to the same assignee as the present invention and which is incorporated by reference herein. Other two dimensional bar code symbologies include Code 1 and Maxicode, which are referred to as matrix codes.
Both one-dimensional and two-dimensional bar code symbols are typically read by optical scanning techniques, such as scanning laser beams, and the resulting electrical signals are then decoded to recover the data encoded in the symbol. In particular, two-dimensional bar code symbols such as those in the PDF417 symbology are advantageously scanned by a two-dimensional rastering laser pattern, which is comprised of a series of horizontal scans repeatedly swept in a vertical direction, as described in U.S. Pat. Nos. 4,816,661 and 5,235,167, which patents are assigned to the assignee of the present application and are incorporated by reference herein. When scanning and decoding a two-dimensional bar code symbol, however, the horizontal scan lines of the laser raster must be aligned substantially with the horizontal rows of the symbol, usually within .+-.3 as shown in FIG. 1A. In FIG. 1A, the laser scan lines 1 form a field of view and are parallel with the horizontally located rows of a PDF417 symbol 3, which will allow successful decoding (in practice, the laser scanning device generates many more closely spaced scan lines 1 than actually shown in FIG. 1A, which has been simplified for purposes of clear illustration).
In FIG. 1B, however, the symbol 3a is tilted with respect to the scan lines 1 in the field of view such that the symbol 3a cannot be successfully decoded. Although a two-dimensional bar code such as PDF417 allows some deviation, the orientation of the field of view 1 must still be less than some maximum angle relative to the rows of the symbol.
When using a hand-held laser rastering scanner, it is fairly simple for the operator to physically align the raster pattern in the field of view with the two-dimensional symbol by rotating the reader and/or the object bearing the symbol until the requisite alignment of the field of view is obtained visually and the symbol is successfully read and decoded. There are many applications, however, in which it is desirable to be able to read and decode a two-dimensional bar code symbol that may be randomly oriented without having to manually move the reader such that the field of view is aligned with rows of the symbol. For example, in an industrial environment, the symbol may be located on an object moving along a conveyor belt where the reader views the symbol from above. Thus, the symbol may be in any orientation relative to the field of view of the reader. In addition, in a retail point-of-sale environment, the symbol may be located on an item presented to a cashier for purchase. The cashier typically puts the item bearing the symbol under a presentation scan lamp, which provides the appropriate laser scanning pattern. In thus desirable in this situation to allow the cashier to quickly present the item under the scan lamp without having to align the symbol with the raster pattern.
Bar code symbol reading devices are also known in the art which are based upon charge coupled device (CCD) imaging technology. For example, a two dimensional CCD array comprised of 512.times.512 elements may be used to capture an image of the entire target bar code symbol simultaneously, and the electric charge stored in each element as a function of the amount of light sensed by an area covered by each element is shifted out serially to form electric signals for further processing, digitizing and decoding. Image processing techniques allow such a CCD array to be used to read misoriented bar code symbols. For example, U.S. Pat. No. 5,319,181, issued to the assignee of the present invention, describes a technique to implement a CCD camera to capture a PDF417 symbol, store the image data in memory, and perform virtual scanning of the image data to determine the proper orientation of the symbol and enable successful decoding. These techniques, while satisfactory in many applications, do not allow high speed reading since the image memory must be repeatedly accessed in a random access manner. There is thus a need in the art for CCD based bar code symbol reading devices to be able to perform high speed reading of misoriented two dimensional bar code symbols.
It is therefore an object of the present invention to provide a method and apparatus for reading and decoding a two-dimensional bar code symbol regardless of its orientation with respect to the field of view of the symbol reading device.
It is a further object of the present invention to be able to calculate the angle of skew of the misoriented bar code symbol with respect to the field of view of the reading device in order to correct for the misorientation by rotating the field of view to the calculated angle.